package puzzle.projecteuler.p100;

public class Problem076C2 {

	/**
	 * 参考Problem076C
	 * 
	 * Problem076C大概要运行30s，这里的程序使用更加高效的算法，不到1ms。
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		long s = System.currentTimeMillis();
		int m = 100;
		long[] a = init(m);
		System.out.println(p(100, a));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}

	/**
	 * the number of ways to write n as sum of m numbers is p(n,m).
	 * p(n,m) = p(n-1, m-1) + p(n-m, m)
	 * p(n,m) = 0, if n < m
	 * p(n,m) = 1, if n = m
	 * 
	 * 在实际编程的时候，我们将中间结果缓存到一维数组中，可以极大地提高运行速度。
	 * p(n, m) => a[n(n-1)/2 + m]
	 * 
	 * 而 p(n) = p(n,2) + ... + p(n,n)
	 * 
	 * @param n
	 * @return
	 */
	public static long p(int n, long[] a) {
		int p = 0;
		for (int i = 2; i <= n; i ++) {
			p += a[k(n,i)];
		}
		return p;
	}
	
	public static long[] init(int m) {
		//初始化数组
		int len = m*(m+1)/2+1;
		long[] a = new long[len];
		a[0] = 0;
		for (int i = 1; i <= m; i ++) {
			for (int j = 1; j <= i; j ++) {
				a[k(i,j)] = (v(i-1, j-1, a) + v(i-j, j, a));
			}
		}
		return a;
	}
	
	public static int k(int n, int m) {
		return n*(n-1)/2 + m;
	}
	
	public static long v(int n, int m, long[] a) {
		if (n <= 0 || m <= 0) {
			return 0;
		} else if (n < m) {
			return 0;
		} else if (n == m) {
			return 1;
		} else {
			return a[k(n,m)];
		}
	}
}
